package leetcode.code0812;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution implements IDebug {

	public double largestTriangleArea(int[][] points) {
		int len = points.length;
		double ans = 0;
		for (int i = 0; i < len; i++) {
			int[] p1 = points[i];
			for (int j = i + 1; j < len; j++) {
				int[] p2 = points[j];
				for (int k = j + 1; k < len; k++) {
					int[] p3 = points[k];
					ans = Math.max(ans, area(p1, p2, p3));
				}
			}
		}
		return ans;
	}

	private double area(int[] p1, int[] p2, int[] p3) {
		if ((p1[0] == p2[0] && p2[0] == p3[0]) || (p1[1] == p2[1] && p2[1] == p3[1])) {
			return 0;
		}
		double d1 = this.dist(p1, p2);
		double d2 = this.dist(p1, p3);
		double d3 = this.dist(p2, p3);
		return area(d1, d2, d3);
	}

	private double area(double d1, double d2, double d3) {
		double a = 0, b = 0, c = 0;
		if (d1 > d2 && d1 > d3) {
			a = d1;
			b = d2;
			c = d3;
		} else if (d2 > d1 && d2 > d3) {
			a = d2;
			b = d1;
			c = d3;
		} else {
			a = d3;
			b = d1;
			c = d2;
		}
		double x = (Math.abs(b * b - c * c) / a + a) / 2;
		double y = a - x;
		double p = Math.max(b, c);
		double q = Math.max(x, y);
		double h = Math.sqrt(p * p - q * q);
		return h * a / 2;
	}

	private double dist(int[] p1, int[] p2) {
		int d1 = p1[0] - p2[0];
		int d2 = p1[1] - p2[1];
		return Math.sqrt(d1 * d1 + d2 * d2);
	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.largestTriangleArea(H.str2array1("[[0,0],[0,1],[1,0],[0,2],[2,0]]"));

	}

}
